package _18_剑指OfferII;

public class _001_剑指OfferII整数除法 {

    public static void main(String[] args) {

        _001_剑指OfferII整数除法 v = new _001_剑指OfferII整数除法();

        //
        System.out.println(-Integer.MIN_VALUE);


    }

    public int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1) return Integer.MAX_VALUE;
        boolean negative = (a ^ b) < 0;
        a = Math.abs(a);
        b = Math.abs(b);
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            if (a >>> i - b >= 0) {
                a -= b << i;
                res += 1 << i;
            }
        }
        return negative? -res: res;
    }

    // 由于减法是一个一个减的，那么最多会减去Integer.MIN_VALUE次， 所以数据规模是10^10次方
    public int divide3(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1) return Integer.MAX_VALUE;
        boolean negative = (a ^ b) < 0;
        if (a > 0) a = -a;
        if (b > 0) b = -b;
        int res = 0;
        while (a <= b) {
            int value = b;
            int k = 1;
            while (value >= 0xc0000000 && a <= value + value) {
                value += value;
                k += k;
            }

            a -= value;
            res += k;
        }
        return negative? -res: res;
    }

    // 边界情况考虑
    // 由于int类型的最小值取abs，装换还是本身，所以不可取
    // 我们可以将所有的数据装换成负数
    public int divide2(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1) return Integer.MIN_VALUE;
        int symbol = ((a ^ b) < 0)? -1: 1;
        if (a > 0) a = -a;
        if (b > 0) b = -b;
        int res = 0;
        while (a <= b) {
            a -= b;
            res++;
        }
        return symbol * res;
    }

    // 由于两个整数除法，也就是由多少个除数加余数可以组成被除数
    // 所以可以使用减法来代替
    public int divide1(int a, int b) {
        // 没有考虑正负数情况
        int symbol = ((a ^ b) < 0)? -1: 1;
        a = Math.abs(a);
        b = Math.abs(b);
        int res = 0;
        while (a >= b) {
            a -= b;
            res++;
        }
        return symbol * res;
    }

}
